Conventionally, cyclic codes such as a Hamming code, CRC, Fire code, BCH code, Reed-Solomon code, and the like are used in many communication systems and recording systems since they are easy to handle.
As shown in Hideki Imai, “Coding theory”, the Institute of Electronics, Information and Communication Engineers, a circuit shown in FIG. 1 is prevalently used as an error detector for these cyclic codes. The circuit shown in FIG. 1 executes a process given by equation (3) that computes a remainder S(x) (to be referred to as a syndrome hereinafter) as a result of dividing a received word R(x) given by equation (1) as an input by a generator polynomial G(x) given by equation (2). Note that R(x) is designed so that the remainder of division by G(x) becomes zero if there is no error.R(x)=RN−1·xN−1+RN−2·xN−2+ . . . +R1·x+R0  (1)G(x)=xm+gm−1·xm−1+ . . . +g1·x+g0  (2)S(x)=R(x)·xm mod G(x)  (3)
The circuit shown in FIG. 1 operates for every unit times (clocks). In the following description, each rectangle expressed by ri (i=0, . . . , m−1) indicates a delay element (register) for one unit time. Also, each rectangle expressed by gi is a multiplier which multiplies an input by gi, and outputs the product (if gi=0, the connection itself is not required; if gi=1, the multiplier is not required, and only the connection is required). Also, “+” indicates an EXOR (exclusive OR) arithmetic unit (which is adopted since arithmetic operations on the Galois field GFS(q) will be examined; in general, a subtractor is used). “NOR” indicates a NOR arithmetic unit.
When Rj (j=N−1, . . . , 0) has been input to this circuit every unit time in turn from higher degrees, if no error has occurred, S(x)=0 is obtained, i.e., all registers ri (i=0, . . . , m−1) become “0”. On the other hand, if an error has occurred, since S(x)≠0, and the NOR arithmetic unit output is not zero, it can be detected that an error has occurred in the received word. Upon forming an encoder which not only detects any error but corrects it, a circuit with an arrangement in FIG. 2 in which a NOR circuit 20 for detecting a specific pattern and an N-bit buffer 22 are added to FIG. 1 is used, and executes the following process.
A right NOR circuit 21 detects “0”, and if S(x)=0 after the same process as in FIG. 1, the process terminates with no error. However, if S(x)≠0, shift registers are further kept shifted up to a maximum of N times with an input “0”, and when a left NOR circuit 20 detects that the values of the shift registers have become a specific pattern based on a code, “1” is output to correct an error of an N-bit delayed received word. Since one shift process of the shift register corresponds to a computation for computing a remainder by multiplying S(x) by x and dividing the product by G(x), an arithmetic operation:E(x)=S(x)·xj mod G(x) (j=0, . . . , N−1)  (4)is made for each shift, i.e., for each j, and a received symbol RN−j when E(x) has become a specific pattern undergoes error correction. For example, if a single error has occurred at a position N−i, we have:S(x)=x−1+m mod G(x)and the (i−1)-th shift (j=i−1) yields:E(x)=S(x)·xi−1 mod G(x)=xm−1Hence, the left NOR circuit 20 detects:rm−j=0(j=2, . . . m)rm−1=1
Furthermore, when cyclic codes are used in practice, a coded word is normally shortened (see “Coding Theory”). Such code is equivalent to a cyclic code in which symbols of higher degrees of equation (1) are “0”, and the correcting capability of the code remains intact. Such code is called a shortened cyclic code. For example, a generator polynomialG(x)=x8+x2+x+1used in header error control of ATM (Asynchronous Transfer Mode) that has received a lot of attention as the next-generation communication scheme has a CRC code lengthN=27=1=127bits. Normally such code is shortened to about 40 bits. In the following description, N represents the code length of a cyclic code specified by the generator polynomial G(x), and n represents the code length obtained by shortening the code length N.
Upon decoding a shortened cyclic code by the circuit shown in FIG. 2, after the received word R(x) is input, a maximum of N shifts and a buffer that stores the received word are required. The detector shown in FIG. 1 can be used in synchronization detection. In this case, a coded word is shifted in turn in increments of 1 bit to determine a new start position, and a coded word from the start position where no error is detected is adopted to synchronize each coded word.
Thereinafter, a term “synchronization detection” means to detect the start position (and/or end position) of code sequence.
The synchronization detection operation will be explained below using FIG. 3.
If one coded word is defined by the first start position to the first end position in FIG. 3, the coded word is expressed by:c1(x)=c1·xn−1+c2·xn−2+ . . . +cn−1·x+cn
A syndrome s1(x) upon dividing this coded word by the generator polynomial given by equation (2) is expressed by:s1(x)=c1(x)·xm mod G(x)
If c1(x) is a correct coded word, s1(x)=0, and the coded word is synchronized. However, if s1(x)≠0, since c1(x) is not a correct coded word, a syndrome s2(x) for a coded word c2(x) from the second start position to the second end position is computed by:c2(x)=c2·xn−1+c3·xn−2+ . . . +cn·x+cn+1s2(x)=c2(x)·xm mod G(x)
Furthermore, if si−1(x)≠0(i=3, . . . ), a syndrome s1(x) for ci(x) given by equation (6) is computed by equation (7), and such computation is repeated until si(x)=0, i.e., synchronization is attained.ci(x)=ci·xn−1+ci+1·xn−2+ . . . +ci+n−2·x+ci+n−1  (6)si(x)=ci(x)·xm mod G(x)  (7)
Therefore, in order to implement this synchronization process, synchronization detection can be achieved using a plurality of circuits shown in FIG. 1 for each si(x) (i=1, . . . ).
On the other hand, since the decoder shown in FIG. 2 can also detect s(x)=0, if the same operations are made using a plurality of circuits shown in FIG. 2 in place of the detector in FIG. 1, the decoder shown in FIG. 2 can be used as a synchronization detection circuit.
However, since the aforementioned synchronization circuit uses a plurality of detectors or decoders, it requires a large circuit scale.